package sorttest;

import java.util.Arrays;

/**
 * @author small瑞
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] tr = new int[10];
        for(int i = 0 ; i < 10 ; i++){
            tr[i] = (int)(Math.random()*100);
        }
        System.out.println(Arrays.toString(QuickM(tr,0,9)));
    }
    static int []QuickM(int[] arr , int s , int e ){
        if(arr.length<1 || s <0 || e>=arr.length || s > e) {
            return null;
        }
        int q = QuickQ(arr,s,e);
        if(q > s){
            QuickM(arr,s,q-1);
        }
        if(q < e){
            QuickM(arr,q+1,e);
        }
        return arr;
    }
    static int QuickQ(int[] arr , int s , int e ){
        int pro = s + (int)(Math.random()*(e-s));
        int index = s-1;
        swap(arr,pro,e);
        for(int i = s ; i <=e ; i++){
            if(arr[i] <= arr[e]){
                index++;
                if(index <=i){
                    /*
                    arr[index]^=arr[i];
                    arr[i]^=arr[index];
                    arr[index]^=arr[i];
                     */
                    swap(arr,index,i);
                }
            }
        }
        return index;
    }
    static int[] swap(int[]arr,int i ,int j){
        int temp ;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
}
